{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Reinforcement Learning for seq2seq\n",
    "\n",
    "This time we'll solve a problem of transсribing Hebrew words in English, also known as g2p (grapheme2phoneme)\n",
    "\n",
    " * word (sequence of letters in source language) -> translation (sequence of letters in target language)\n",
    "\n",
    "Unlike what most deep learning practitioners do, we won't only train it to maximize likelihood of correct translation, but also employ reinforcement learning to actually teach it to translate with as few errors as possible.\n",
    "\n",
    "\n",
    "### About the task\n",
    "\n",
    "One notable property of Hebrew is that it's a consonant language. That is, there are no vowels in the written language. One could represent vowels with diacritics above consonants, but you don't expect people to do that in everyday life.\n",
    "\n",
    "Therefore, some Hebrew characters will correspond to several English letters and others - to none, so we should use encoder-decoder architecture to figure that out.\n",
    "\n",
    "![img](https://esciencegroup.files.wordpress.com/2016/03/seq2seq.jpg)\n",
    "_(img: esciencegroup.files.wordpress.com)_\n",
    "\n",
    "Encoder-decoder architectures are about converting anything to anything, including\n",
    " * Machine translation and spoken dialogue systems\n",
    " * [Image captioning](https://cocodataset.org/#captions-2015) and [image2latex](https://htmlpreview.github.io/?https://github.com/openai/requests-for-research/blob/master/_requests_for_research/im2latex.html) (convolutional encoder, recurrent decoder)\n",
    " * Generating [images by captions](https://arxiv.org/abs/1511.02793) (recurrent encoder, convolutional decoder)\n",
    " * Grapheme2phoneme - convert words to transcripts\n",
    "\n",
    "We chose simplified __Hebrew->English__ machine translation for words and short phrases (character-level), as it is relatively quick to train even without a gpu cluster."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "if 'google.colab' in sys.modules:\n",
    "    !wget https://raw.githubusercontent.com/yandexdataschool/Practical_RL/master/week07_seq2seq/basic_model_torch.py -O basic_model_torch.py\n",
    "    !wget https://raw.githubusercontent.com/yandexdataschool/Practical_RL/master/week07_seq2seq/main_dataset.txt -O main_dataset.txt\n",
    "    !wget https://raw.githubusercontent.com/yandexdataschool/Practical_RL/master/week07_seq2seq/voc.py -O voc.py\n",
    "    !pip3 install torch==1.0.0 nltk editdistance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# If True, only translates phrases shorter than 20 characters (way easier).\n",
    "EASY_MODE = True\n",
    "# Useful for initial coding.\n",
    "# If false, works with all phrases (please switch to this mode for homework assignment)\n",
    "\n",
    "# way we translate. Either \"he-to-en\" or \"en-to-he\"\n",
    "MODE = \"he-to-en\"\n",
    "# maximal length of _generated_ output, does not affect training\n",
    "MAX_OUTPUT_LENGTH = 50 if not EASY_MODE else 20\n",
    "REPORT_FREQ = 100                          # how often to evaluate validation score"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 1: preprocessing\n",
    "\n",
    "We shall store dataset as a dictionary\n",
    "`{ word1:[translation1,translation2,...], word2:[...],...}`.\n",
    "\n",
    "This is mostly due to the fact that many words have several correct translations.\n",
    "\n",
    "We have implemented this thing for you so that you can focus on more interesting parts."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from collections import defaultdict\n",
    "word_to_translation = defaultdict(list)  # our dictionary\n",
    "\n",
    "bos = '_'\n",
    "eos = ';'\n",
    "\n",
    "with open(\"main_dataset.txt\", encoding=\"utf-8\") as fin:\n",
    "    for line in fin:\n",
    "\n",
    "        en, he = line[:-1].lower().replace(bos, ' ').replace(eos,\n",
    "                                                             ' ').split('\\t')\n",
    "        word, trans = (he, en) if MODE == 'he-to-en' else (en, he)\n",
    "\n",
    "        if len(word) < 3:\n",
    "            continue\n",
    "        if EASY_MODE:\n",
    "            if max(len(word), len(trans)) > 20:\n",
    "                continue\n",
    "\n",
    "        word_to_translation[word].append(trans)\n",
    "\n",
    "print(\"size = \", len(word_to_translation))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# get all unique lines in source language\n",
    "all_words = np.array(list(word_to_translation.keys()))\n",
    "# get all unique lines in translation language\n",
    "all_translations = np.array(list(set(\n",
    "    [ts for all_ts in word_to_translation.values() for ts in all_ts])))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### split the dataset\n",
    "\n",
    "We hold out 10% of all words to be used for validation.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.model_selection import train_test_split\n",
    "train_words, test_words = train_test_split(\n",
    "    all_words, test_size=0.1, random_state=42)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Building vocabularies\n",
    "\n",
    "We now need to build vocabularies that map strings to token ids and vice versa. We're gonna need these fellas when we feed training data into the model or convert output matrices into English words."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from voc import Vocab\n",
    "inp_voc = Vocab.from_lines(''.join(all_words), bos=bos, eos=eos, sep='')\n",
    "out_voc = Vocab.from_lines(''.join(all_translations), bos=bos, eos=eos, sep='')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Here's how you cast lines into ids and backwards.\n",
    "batch_lines = all_words[:5]\n",
    "batch_ids = inp_voc.to_matrix(batch_lines)\n",
    "batch_lines_restored = inp_voc.to_lines(batch_ids)\n",
    "\n",
    "print(\"lines\")\n",
    "print(batch_lines)\n",
    "print(\"\\nwords to ids (0 = bos, 1 = eos):\")\n",
    "print(batch_ids)\n",
    "print(\"\\nback to words\")\n",
    "print(batch_lines_restored)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Draw word/translation length distributions to estimate the scope of the task."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "plt.figure(figsize=[8, 4])\n",
    "plt.subplot(1, 2, 1)\n",
    "plt.title(\"words\")\n",
    "plt.hist(list(map(len, all_words)), bins=20)\n",
    "\n",
    "plt.subplot(1, 2, 2)\n",
    "plt.title('translations')\n",
    "plt.hist(list(map(len, all_translations)), bins=20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 3: deploy encoder-decoder (1 point)\n",
    "\n",
    "__assignment starts here__\n",
    "\n",
    "Our architecture consists of two main blocks:\n",
    "* Encoder reads words character by character and outputs code vector (usually a function of last RNN state)\n",
    "* Decoder takes that code vector and produces translations character by character\n",
    "\n",
    "Then it gets fed into a model that follows this simple interface:\n",
    "* __`model(inp, out, **flags) -> logp`__ - takes symbolic int32 matrices of Hebrew words and their English translations. Computes the log-probabilities of all possible English characters given English prefixes and Hebrew word.\n",
    "* __`model.translate(inp, **flags) -> out, logp`__ - takes symbolic int32 matrix of Hebrew words, produces output tokens sampled from the model and output log-probabilities for all possible tokens at each tick.\n",
    "  * if given flag __`greedy=True`__, takes most likely next token at each iteration. Otherwise, samples with next token probabilities predicted by model.\n",
    "\n",
    "That's all! It's as hard as it gets. With those two methods alone, you can implement all kinds of prediction and training."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import torch\n",
    "import torch.nn as nn\n",
    "import torch.nn.functional as F"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from basic_model_torch import BasicTranslationModel\n",
    "model = BasicTranslationModel(inp_voc, out_voc,\n",
    "                              emb_size=64, hid_size=256)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Play around with symbolic_translate and symbolic_score\n",
    "inp = torch.tensor(np.random.randint(0, 10, [3, 5]), dtype=torch.int64)\n",
    "out = torch.tensor(np.random.randint(0, 10, [3, 5]), dtype=torch.int64)\n",
    "\n",
    "# translate inp (with untrained model)\n",
    "sampled_out, logp = model.translate(inp, greedy=False)\n",
    "\n",
    "print(\"Sample translations:\\n\", sampled_out)\n",
    "print(\"Log-probabilities at each step:\\n\", logp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# score logp(out | inp) with untrained input\n",
    "logp = model(inp, out)\n",
    "print(\"Symbolic_score output:\\n\", logp)\n",
    "\n",
    "print(\"Log-probabilities of output tokens:\\n\",\n",
    "      torch.gather(logp, dim=2, index=out[:, :, None]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def translate(lines, max_len=MAX_OUTPUT_LENGTH):\n",
    "    \"\"\"\n",
    "    You are given a list of input lines.\n",
    "    Make your neural network translate them.\n",
    "    :return: a list of output lines\n",
    "    \"\"\"\n",
    "    # Convert lines to a matrix of indices\n",
    "    lines_ix = inp_voc.to_matrix(lines)\n",
    "    lines_ix = torch.tensor(lines_ix, dtype=torch.int64)\n",
    "\n",
    "    # Compute translations in form of indices\n",
    "    trans_ix = <YOUR CODE>\n",
    "\n",
    "    # Convert translations back into strings\n",
    "    return out_voc.to_lines(trans_ix.data.numpy())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Sample inputs:\", all_words[:3])\n",
    "print(\"Dummy translations:\", translate(all_words[:3]))\n",
    "trans = translate(all_words[:3])\n",
    "\n",
    "assert translate(all_words[:3]) == translate(\n",
    "    all_words[:3]), \"make sure translation is deterministic (use greedy=True and disable any noise layers)\"\n",
    "assert type(translate(all_words[:3])) is list and (type(translate(all_words[:1])[0]) is str or type(\n",
    "    translate(all_words[:1])[0]) is unicode), \"translate(lines) must return a sequence of strings!\"\n",
    "# note: if translation freezes, make sure you used max_len parameter\n",
    "print(\"Tests passed!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Scoring function\n",
    "\n",
    "LogLikelihood is a poor estimator of model performance.\n",
    "* If we predict zero probability once, it shouldn't ruin the entire model.\n",
    "* It is enough to learn just one translation if there are several correct ones.\n",
    "* What matters is how many mistakes model's gonna make when it translates!\n",
    "\n",
    "Therefore, we will use minimal Levenshtein distance. It measures how many characters do we need to add/remove/replace from model translation to make it perfect. Alternatively, one could use character-level BLEU/RougeL or other similar metrics.\n",
    "\n",
    "The catch here is that Levenshtein distance is not differentiable: it isn't even continuous. We can't train our neural network to maximize it by gradient descent."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import editdistance  # !pip install editdistance\n",
    "\n",
    "\n",
    "def get_distance(word, trans):\n",
    "    \"\"\"\n",
    "    A function that takes word and predicted translation\n",
    "    and evaluates (Levenshtein's) edit distance to closest correct translation\n",
    "    \"\"\"\n",
    "    references = word_to_translation[word]\n",
    "    assert len(references) != 0, \"wrong/unknown word\"\n",
    "    return min(editdistance.eval(trans, ref) for ref in references)\n",
    "\n",
    "\n",
    "def score(words, bsize=100):\n",
    "    \"\"\"a function that computes levenshtein distance for bsize random samples\"\"\"\n",
    "    assert isinstance(words, np.ndarray)\n",
    "\n",
    "    batch_words = np.random.choice(words, size=bsize, replace=False)\n",
    "    batch_trans = translate(batch_words)\n",
    "\n",
    "    distances = list(map(get_distance, batch_words, batch_trans))\n",
    "\n",
    "    return np.array(distances, dtype='float32')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# should be around 5-50 and decrease rapidly after training :)\n",
    "[score(test_words, 10).mean() for _ in range(5)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Step 2: Supervised pre-training (2 points)\n",
    "\n",
    "Here we define a function that trains our model through maximizing log-likelihood a.k.a. minimizing crossentropy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "\n",
    "def sample_batch(words, word_to_translation, batch_size):\n",
    "    \"\"\"\n",
    "    sample random batch of words and random correct translation for each word\n",
    "    example usage:\n",
    "    batch_x,batch_y = sample_batch(train_words, word_to_translations,10)\n",
    "    \"\"\"\n",
    "    # choose words\n",
    "    batch_words = np.random.choice(words, size=batch_size)\n",
    "\n",
    "    # choose translations\n",
    "    batch_trans_candidates = list(map(word_to_translation.get, batch_words))\n",
    "    batch_trans = list(map(random.choice, batch_trans_candidates))\n",
    "    return batch_words, batch_trans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "bx, by = sample_batch(train_words, word_to_translation, batch_size=3)\n",
    "print(\"Source:\")\n",
    "print(bx)\n",
    "print(\"Target:\")\n",
    "print(by)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from basic_model_torch import infer_length, infer_mask, to_one_hot\n",
    "\n",
    "\n",
    "def compute_loss_on_batch(input_sequence, reference_answers):\n",
    "    \"\"\" Compute crossentropy loss given a batch of sources and translations \"\"\"\n",
    "    input_sequence = torch.tensor(inp_voc.to_matrix(input_sequence), dtype=torch.int64)\n",
    "    reference_answers = torch.tensor(out_voc.to_matrix(reference_answers), dtype=torch.int64)\n",
    "\n",
    "    # Compute log-probabilities of all possible tokens at each step. Use model interface.\n",
    "    logprobs_seq = <YOUR CODE>\n",
    "\n",
    "    # compute elementwise crossentropy as negative log-probabilities of reference_answers.\n",
    "    crossentropy = - \\\n",
    "        torch.sum(logprobs_seq *\n",
    "                  to_one_hot(reference_answers, len(out_voc)), dim=-1)\n",
    "    assert crossentropy.dim(\n",
    "    ) == 2, \"please return elementwise crossentropy, don't compute mean just yet\"\n",
    "\n",
    "    # average with mask\n",
    "    mask = infer_mask(reference_answers, out_voc.eos_ix)\n",
    "    loss = torch.sum(crossentropy * mask) / torch.sum(mask)\n",
    "\n",
    "    return loss"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# test it\n",
    "loss = compute_loss_on_batch(*sample_batch(train_words, word_to_translation, 3))\n",
    "print('loss = ', loss)\n",
    "\n",
    "assert loss.item() > 0.0\n",
    "loss.backward()\n",
    "for w in model.parameters():\n",
    "    assert w.grad is not None and torch.max(torch.abs(w.grad)).item() != 0, \\\n",
    "        \"Loss is not differentiable w.r.t. a weight with shape %s. Check comput_loss_on_batch.\" % (\n",
    "            w.size(),)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Actually train the model\n",
    "\n",
    "Minibatches and stuff..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.display import clear_output\n",
    "from tqdm import tqdm, trange  # or use tqdm_notebook,tnrange\n",
    "\n",
    "loss_history = []\n",
    "editdist_history = []\n",
    "entropy_history = []\n",
    "opt = torch.optim.Adam(model.parameters())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "\n",
    "for i in trange(25000):\n",
    "    loss = compute_loss_on_batch(*sample_batch(train_words, word_to_translation, 32))\n",
    "\n",
    "    # train with backprop\n",
    "    loss.backward()\n",
    "    opt.step()\n",
    "    opt.zero_grad()\n",
    "\n",
    "    loss_history.append(loss.item())\n",
    "\n",
    "    if (i+1) % REPORT_FREQ == 0:\n",
    "        clear_output(True)\n",
    "        current_scores = score(test_words)\n",
    "        editdist_history.append(current_scores.mean())\n",
    "        print(\"llh=%.3f, mean score=%.3f\" %\n",
    "              (np.mean(loss_history[-10:]), np.mean(editdist_history[-10:])))\n",
    "        plt.figure(figsize=(12, 4))\n",
    "        plt.subplot(131)\n",
    "        plt.title('train loss / traning time')\n",
    "        plt.plot(loss_history)\n",
    "        plt.grid()\n",
    "        plt.subplot(132)\n",
    "        plt.title('val score distribution')\n",
    "        plt.hist(current_scores, bins=20)\n",
    "        plt.subplot(133)\n",
    "        plt.title('val score / traning time (lower is better)')\n",
    "        plt.plot(editdist_history)\n",
    "        plt.grid()\n",
    "        plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__How to interpret the plots:__\n",
    "\n",
    "* __Train loss__ - that's your model's crossentropy over minibatches. It should go down steadily. Most importantly, it shouldn't be NaN :)\n",
    "* __Val score distribution__ - distribution of translation edit distance (score) within batch. It should move to the left over time.\n",
    "* __Val score / training time__ - it's your current mean edit distance. This plot is much whimsier than loss, but make sure it goes below 8 by 2500 steps.\n",
    "\n",
    "If it doesn't, first try to re-create both model and opt. You may have changed its weight too much while debugging. If that doesn't help, it's debugging time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for word in train_words[:10]:\n",
    "    print(\"%s -> %s\" % (word, translate([word])[0]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_scores = []\n",
    "for start_i in trange(0, len(test_words), 32):\n",
    "    batch_words = test_words[start_i:start_i+32]\n",
    "    batch_trans = translate(batch_words)\n",
    "    distances = list(map(get_distance, batch_words, batch_trans))\n",
    "    test_scores.extend(distances)\n",
    "\n",
    "print(\"Supervised test score:\", np.mean(test_scores))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Self-critical policy gradient (2 points)\n",
    "\n",
    "In this section you'll implement algorithm called self-critical sequence training (here's an [article](https://arxiv.org/abs/1612.00563)).\n",
    "\n",
    "The algorithm is a vanilla policy gradient with a special baseline.\n",
    "\n",
    "$$ \\nabla J = E_{x \\sim p(s)} E_{y \\sim \\pi(y|x)} \\nabla log \\pi(y|x) \\cdot (R(x,y) - b(x)) $$\n",
    "\n",
    "Here reward R(x,y) is a __negative levenshtein distance__ (since we minimize it). The baseline __b(x)__ represents how well model fares on word __x__.\n",
    "\n",
    "In practice, this means that we compute baseline as a score of greedy translation, $b(x) = R(x,y_{greedy}(x)) $.\n",
    "\n",
    "![img](https://github.com/yandexdataschool/Practical_RL/raw/master/yet_another_week/_resource/scheme.png)\n",
    "\n",
    "\n",
    "Luckily, we already obtained the required outputs: `model.greedy_translations, model.greedy_mask` and we only need to compute levenshtein using `compute_levenshtein` function.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def compute_reward(input_sequence, translations):\n",
    "    \"\"\" computes sample-wise reward given token ids for inputs and translations \"\"\"\n",
    "    distances = list(map(get_distance,\n",
    "                         inp_voc.to_lines(input_sequence.data.numpy()),\n",
    "                         out_voc.to_lines(translations.data.numpy())))\n",
    "    # use negative levenshtein distance so that larger reward means better policy\n",
    "    return - torch.tensor(distances, dtype=torch.int64)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def scst_objective_on_batch(input_sequence, max_len=MAX_OUTPUT_LENGTH):\n",
    "    \"\"\" Compute pseudo-loss for policy gradient given a batch of sources \"\"\"\n",
    "    input_sequence = torch.tensor(inp_voc.to_matrix(input_sequence), dtype=torch.int64)\n",
    "\n",
    "    # use model to __sample__ symbolic translations given input_sequence\n",
    "    sample_translations, sample_logp = <YOUR CODE>\n",
    "    # use model to __greedy__ symbolic translations given input_sequence\n",
    "    greedy_translations, greedy_logp = <YOUR CODE>\n",
    "\n",
    "    # compute rewards and advantage\n",
    "    rewards = compute_reward(input_sequence, sample_translations)\n",
    "    baseline = <YOUR CODE: compute __negative__ levenshtein for greedy mode>\n",
    "\n",
    "    # compute advantage using rewards and baseline\n",
    "    advantage =  <YOUR CODE>\n",
    "\n",
    "    # compute log_pi(a_t|s_t), shape = [batch, seq_length]\n",
    "    logp_sample = <YOUR CODE>\n",
    "\n",
    "    # ^-- hint: look at how crossentropy is implemented in supervised learning loss above\n",
    "    # mind the sign - this one should not be multiplied by -1 :)\n",
    "\n",
    "    # policy gradient pseudo-loss. Gradient of J is exactly policy gradient.\n",
    "    J = logp_sample * advantage[:, None]\n",
    "\n",
    "    assert J.dim() == 2, \"please return elementwise objective, don't compute mean just yet\"\n",
    "\n",
    "    # average with mask\n",
    "    mask = infer_mask(sample_translations, out_voc.eos_ix)\n",
    "    loss = - torch.sum(J * mask) / torch.sum(mask)\n",
    "\n",
    "    # regularize with negative entropy. Don't forget the sign!\n",
    "    # note: for entropy you need probabilities for all tokens (sample_logp), not just logp_sample\n",
    "    entropy = <YOUR CODE: compute entropy matrix of shape[batch, seq_length], H = -sum(p*log_p), don't forget the sign!>\n",
    "    # hint: you can get sample probabilities from sample_logp using math :)\n",
    "\n",
    "    assert entropy.dim(\n",
    "    ) == 2, \"please make sure elementwise entropy is of shape [batch,time]\"\n",
    "\n",
    "    reg = - 0.01 * torch.sum(entropy * mask) / torch.sum(mask)\n",
    "\n",
    "    return loss + reg, torch.sum(entropy * mask) / torch.sum(mask)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Policy gradient training\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "entropy_history = [np.nan] * len(loss_history)\n",
    "opt = torch.optim.Adam(model.parameters(), lr=1e-5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in trange(100000):\n",
    "    loss, ent = scst_objective_on_batch(\n",
    "        sample_batch(train_words, word_to_translation, 32)[0])  # [0] = only source sentence\n",
    "\n",
    "    # train with backprop\n",
    "    loss.backward()\n",
    "    opt.step()\n",
    "    opt.zero_grad()\n",
    "\n",
    "    loss_history.append(loss.item())\n",
    "    entropy_history.append(ent.item())\n",
    "\n",
    "    if (i+1) % REPORT_FREQ == 0:\n",
    "        clear_output(True)\n",
    "        current_scores = score(test_words)\n",
    "        editdist_history.append(current_scores.mean())\n",
    "        plt.figure(figsize=(12, 4))\n",
    "        plt.subplot(131)\n",
    "        plt.title('val score distribution')\n",
    "        plt.hist(current_scores, bins=20)\n",
    "        plt.subplot(132)\n",
    "        plt.title('val score / traning time')\n",
    "        plt.plot(editdist_history)\n",
    "        plt.grid()\n",
    "        plt.subplot(133)\n",
    "        plt.title('policy entropy / traning time')\n",
    "        plt.plot(entropy_history)\n",
    "        plt.grid()\n",
    "        plt.show()\n",
    "        print(\"J=%.3f, mean score=%.3f\" %\n",
    "              (np.mean(loss_history[-10:]), np.mean(editdist_history[-10:])))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Debugging tips:__\n",
    "<img src=https://github.com/yandexdataschool/Practical_RL/raw/master/yet_another_week/_resource/do_something_scst.png width=400>\n",
    "\n",
    " * As usual, don't expect improvements right away, but in general the model should be able to show some positive changes by 5k steps.\n",
    " * Entropy is a good indicator of many problems.\n",
    "   * If it reaches zero, you may need greater entropy regularizer.\n",
    "   * If it has rapid changes time to time, you may need gradient clipping.\n",
    "   * If it oscillates up and down in an erratic manner... it's perfectly okay for entropy to do so. But it should decrease at the end.\n",
    "\n",
    " * We don't show loss_history cuz it's uninformative for pseudo-losses in policy gradient. However, if something goes wrong you can check it to see if everything isn't a constant zero."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for word in train_words[:10]:\n",
    "    print(\"%s -> %s\" % (word, translate([word])[0]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_scores = []\n",
    "for start_i in trange(0, len(test_words), 32):\n",
    "    batch_words = test_words[start_i:start_i+32]\n",
    "    batch_trans = translate(batch_words)\n",
    "    distances = list(map(get_distance, batch_words, batch_trans))\n",
    "    test_scores.extend(distances)\n",
    "print(\"Supervised test score:\", np.mean(test_scores))\n",
    "\n",
    "# ^^ If you get Out Of MemoryError, please replace this with batched computation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Step 6: Make it actually work (5++ pts)\n",
    "\n",
    "In this section, we want you to finally __restart with EASY_MODE=False__ and experiment to find a good model/curriculum for that task.\n",
    "\n",
    "We recommend you to start with the following architecture\n",
    "\n",
    "```\n",
    "encoder---decoder\n",
    "\n",
    "           P(y|h)\n",
    "             ^\n",
    " LSTM  ->   LSTM\n",
    "  ^          ^\n",
    " biLSTM  ->   LSTM\n",
    "  ^          ^\n",
    "input       y_prev\n",
    "```\n",
    "\n",
    "__Note:__ you can fit all 4 state tensors of both LSTMs into in a single state - just assume that it contains, for example, [h0, c0, h1, c1] - pack it in encode and update in decode.\n",
    "\n",
    "\n",
    "Here are some cool ideas on what you can do then.\n",
    "\n",
    "__General tips & tricks:__\n",
    "* You will likely need to adjust pre-training time for such a network.\n",
    "* Supervised pre-training may benefit from clipping gradients somehow.\n",
    "* SCST may indulge a higher learning rate in some cases and changing entropy regularizer over time.\n",
    "* It's often useful to save pre-trained model parameters to not re-train it every time you want new policy gradient parameters.\n",
    "* When leaving training for nighttime, try setting REPORT_FREQ to a larger value (e.g. 500) not to waste time on it.\n",
    "\n",
    "__Formal criteria:__\n",
    "To get 5 points, we want you to build an architecture that:\n",
    "* _doesn't consist of single GRU_\n",
    "* _works better_ than single GRU baseline.\n",
    "* We also want you to provide either learning curve or trained model, preferably both\n",
    "* ... and write a brief report or experiment log describing what you did and how it fared.\n",
    "\n",
    "### Attention\n",
    "There's more than one way to connect decoder to encoder\n",
    "  * __Vanilla:__ layer_i of encoder last state goes to layer_i of decoder initial state\n",
    "  * __Every tick:__ feed encoder last state _on every iteration_ of decoder.\n",
    "  * __Attention:__ allow decoder to \"peek\" at one (or several) positions of encoded sequence on every tick.\n",
    "\n",
    "The most effective (and cool) of those is, of course, attention.\n",
    "You can read more about attention [in this nice blog post](https://distill.pub/2016/augmented-rnns/). The easiest way to begin is to use \"soft\" attention with \"additive\" or \"dot-product\" intermediate layers.\n",
    "\n",
    "__Tips__\n",
    "* Model usually generalizes better if you no longer allow decoder to see final encoder state\n",
    "* Once your model made it through several epochs, it is a good idea to visualize attention maps to understand what your model has actually learned\n",
    "\n",
    "* There's more stuff [here](bonus_pytorch.ipynb)\n",
    "* If you opted for hard attention, we recommend [gumbel-softmax](https://blog.evjang.com/2016/11/tutorial-categorical-variational.html) instead of sampling. Also, please make sure soft attention works fine before you switch to hard.\n",
    "\n",
    "### UREX\n",
    "* This is a way to improve exploration in policy-based settings. The main idea is that you find and upweight under-appreciated actions.\n",
    "* Here's [video](https://www.youtube.com/watch?v=fZNyHoXgV7M&feature=youtu.be&t=3444)\n",
    " and an [article](https://arxiv.org/abs/1611.09321).\n",
    "* You may want to reduce batch size 'cuz UREX requires you to sample multiple times per source sentence.\n",
    "* Once you got it working, try using experience replay with importance sampling instead of (in addition to) basic UREX.\n",
    "\n",
    "### Some additional ideas:\n",
    "* (advanced deep learning) It may be a good idea to first train on small phrases and then adapt to larger ones (a.k.a. training curriculum).\n",
    "* (advanced nlp) You may want to switch from raw utf8 to something like unicode or even syllables to make the task easier.\n",
    "* (advanced nlp) Since Hebrew words are written __with vowels omitted__, you may want to use a small Hebrew vowel markup dataset at `he-pron-wiktionary.txt`.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert not EASY_MODE, \"make sure you set EASY_MODE = False at the top of the notebook.\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`[your report/log here or anywhere you please]`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Contributions:__ This notebook is brought to you by\n",
    "* Yandex [MT team](https://tech.yandex.com/translate/)\n",
    "* Denis Mazur ([DeniskaMazur](https://github.com/DeniskaMazur)), Oleg Vasilev ([Omrigan](https://github.com/Omrigan/)), Dmitry Emelyanenko ([TixFeniks](https://github.com/tixfeniks)) and Fedor Ratnikov ([justheuristic](https://github.com/justheuristic/))\n",
    "* Dataset is parsed from [Wiktionary](https://en.wiktionary.org), which is under CC-BY-SA and GFDL licenses.\n"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python",
   "pygments_lexer": "ipython3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
